package 中等.链表;

import util.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 你能尝试使用一趟扫描实现吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 */
public class 删除链表的倒数第N个结点_19 {

    public static void main(String[] args) {

        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        n1.next = n2;
        n2.next = n3;
        efficientRemoveNthFromEnd(n1, 3);

    }

    /**
     * 快慢指针
     * 快指针先走 n-1 个节点，快指针遍历到结尾时，慢指针即为删除的节点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode efficientRemoveNthFromEnd(ListNode head, int n) {
        ListNode slow = head;
        ListNode quick = head;

        for (int i = 0; i < n - 1; i++) {
            quick = quick.next;
        }
        // 保存慢指针的前一个节点，用来删除慢指针
        ListNode preSlow = null;
        while (quick.next != null) {
            quick = quick.next;
            preSlow = slow;
            slow = slow.next;
        }
        // 要删除的是第一个节点
        if (preSlow == null) {
            return head.next;
        }
        preSlow.next = slow.next;
        return head;
    }

    /**
     * 哈希表
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        Map<Integer, ListNode> map = new HashMap<>();
        int total = 0;
        ListNode curNode = head;

        while (curNode != null) {
            total++;
            map.put(total, curNode);
            curNode = curNode.next;
        }

        if (total == 1) {
            return null;
        }
        if (n == total) {
            return map.get(2);
        }

        ListNode delNode = map.get(total - n + 1);
        ListNode preNode = map.get(total - n);

        preNode.next = delNode.next;
        return head;
    }

}
